package se;


import java.util.Collection;
import java.util.Map;
import java.util.Set;

//HashMap1.7 底层链表
public class HashMap_jdk7_Principle {

   public static void main(String[] args) {
      HashMap2<String, Object> hashMap2 = new HashMap2();
      hashMap2.put("3", "我是3");
      hashMap2.put("1", "我是1");
      hashMap2.put("1", "我是111111XXXX");
      hashMap2.put("2", "我是2");

      System.out.println(hashMap2.get("3") + "!!!!!!!");
      System.out.println(hashMap2.get("2") + "!!!!!!!");
      System.out.println(hashMap2.get("1") + "!!!!!!!");
   }

   public static class HashMap2<K, V> implements Map<K, V> {
      private static final int initSize = 4;//初始化容量
      private final Entry[] table = new Entry[initSize];


      private final boolean fuGai = true;

      public static class Entry<K, V> {
         private K k;
         private V v;
         private Entry<K, V> next;

         public Entry(K k, V v) {
            this.k = k;
            this.v = v;
         }
      }

      @Override
      public int size() {
         return 0;
      }

      @Override
      public boolean isEmpty() {
         return false;
      }

      @Override
      public boolean containsKey(Object key) {
         return false;
      }

      @Override
      public boolean containsValue(Object value) {
         return false;
      }

      @Override
      public V get(Object key) {
         int index = indexFor(key.hashCode(), initSize);
         if(table[index] == null) {
            return null;
         }else{
            if(table[index].k.equals(key)){
               return (V) table[index].v;
            }else{
               if(table[index].next == null){
                  return null;
               }else{
                  Entry ofLink = table[index];
                  while (ofLink.next != null) {
                     ofLink = ofLink.next;
                     if (ofLink.k.equals(key)) {//查询此元素下的子元素,并不断的判断是否为目标key,找不到覆盖,找到根据特性覆盖与否
                        return (V) ofLink.v;
                     }
                  }
               }
            }
         }
         return (V) "未命中！";
      }

      public V put(K k, V v) {
         //取此k的hashCode,不同对象的hashCode可能相同,后期是通过equeals方法来兜底的，
         int hashCode = k.hashCode();    //需要对hashCode进行扰动 todo
         System.out.print("hashCode:" + hashCode);
         int index = indexFor(hashCode, initSize); //获取index
         System.out.println(",index:" + index);
         Entry paramEntry = new Entry(k, v);
         if (table[index] == null) {//直接存数据
            table[index] = paramEntry;
         } else if (table[index] != null) {   //数组元素占用,此key可能就是目标
            if (table[index].k.equals(paramEntry.k)) { //此key就是目标
               table[index] = paramEntry;//直接覆盖
            } else {//此key不是目标
               if(table[index].next == null){//说明此数组下无链表
                  table[index] = paramEntry;
               }else{//此数组下有链表元素
                  //头插法插入新元素   头插法为什么会出现死循环 todo
                  boolean found = false;
                  Entry ofLink = table[index];
                  while (ofLink.next != null) {
                     ofLink = ofLink.next;
                     if (ofLink.k.equals(paramEntry.k)) {//查询此元素下的子元素,并不断的判断是否为目标key,找不到覆盖,找到根据特性覆盖与否
                        Entry oldTail = ofLink.next;
                        ofLink.next = paramEntry;
                        paramEntry.next = oldTail;
                        found = true;
                     }
                  }
                  if(!found){//在链表中真的没有此key的话,则在最尾巴插入
                     ofLink.next = paramEntry;
                  }
               }
            }
         }
         for(Entry e : table){
            System.out.print(e + ",");
         }
         System.out.println();
         return v;
      }

      // 获取数组索引
      static final int indexFor(int h, int length) {
         int arrayIndex = h & (length - 1);
         return arrayIndex;//位运算,需要额外处理
      }

      @Override
      public V remove(Object key) {
         return null;
      }

      @Override
      public void putAll(Map<? extends K, ? extends V> m) {

      }

      @Override
      public void clear() {
      }

      @Override
      public Set<K> keySet() {
         return null;
      }

      @Override
      public Collection<V> values() {
         return null;
      }

      @Override
      public Set<Map.Entry<K, V>> entrySet() {
         return null;
      }
   }

}
